/*
 * @lc app=leetcode.cn id=140 lang=javascript
 *
 * [140] 单词拆分 II
 */

// @lc code=start
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {string[]}
 */
var wordBreak = function (s, wordDict) {
  const dict = new Set(wordDict);
  const size = s.length;
  const memo = new Map();
  /**
   * @description: DFS
   * @param {String} s 求解的字符串
   * @param {Number} size 字符串的长度
   * @param {Set} dict 字典
   * @param {Map} memo 存储的下标，优化搜索
   * @param {Number} index 开始的下标
   * @return {[String[]]}
   */
  function dfs(s, size, dict, memo, index) {
    if (memo.has(index)) {
      return memo.get(index);
    }

    const words = [];
    if (index >= size) {
      words.push([]);
    }

    for (let i = index + 1; i <= size; i++) {
      const word = s.substring(index, i);
      if (dict.has(word)) {
        const nextWords = dfs(s, size, dict, memo, i);
        nextWords.forEach((nextWord) => {
          words.push([word, ...nextWord]);
        });
      }
    }

    memo.set(index, words);
    return words;
  }

  return dfs(s, size, dict, memo, 0).map((words) => {
    return words.join(' ');
  });
};
// @lc code=end
